#include <stdio.h>

void test();

int hanoi(int);

void quickSort(int *, int, int);

void quickSort2(int *, int, int);

int main() {
    int arr[] = {4, 3, 8, 2, 1, 7, 5, 6, 9, 0};
    quickSort(arr, 0, 9);
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
        printf("%d ", arr[i]);
    }

    printf("\n");

    int arr2[] = {4, 3, 8, 2, 1, 7, 5, 6, 9, 0};
    quickSort(arr2, 0, 9);
    for (int i = 0; i < sizeof(arr2) / sizeof(arr2[0]); ++i) {
        printf("%d ", arr2[i]);
    }
    return 0;
}

void test() {
    static int a = 20;   //静态变量并不会在函数结束时销毁其值，而是保持
    a += 20;
    printf("%d ", a);
}

/**
 * 汉诺塔
 * 把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
 * 这三根柱子我们就依次命名为A、B、C，现在请你设计一个C语言程序，计算N阶（n片圆盘）汉诺塔移动操作的步数。
 * @param n 圆盘的个数
 * @return 移动的步数
 */
int hanoi(int n) {
    if (n == 1) return 1;
    return 2 * hanoi(n - 1) + 1;
}

/**
 * 快排序算法
 * @param arr 待排序的数组
 * @param left 起始下标
 * @param right 结束下标
 */
void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int base = arr[left];
    int baseL = left, baseR = right;
    while (left < right) {
        while (left < right) {
            if (arr[right] < base) {
                arr[left] = arr[right];
                left++;
                break;
            }
            right--;
        }
        while (left < right) {
            if (arr[left] > base) {
                arr[right] = arr[left];
                right--;
                break;
            }
            left++;
        }
    }
    arr[left] = base;
    quickSort(arr, baseL, left - 1);
    quickSort(arr, left + 1, baseR);
}

//快排序另一种简洁写法
void quickSort2(int arr[], int left, int right) {
    if (left >= right) return;
    int base = arr[left], l = left, r = right;
    while (l < r) {
        while (l < r && arr[r] >= base) r--;
        arr[l] = arr[r];
        while (l < r && arr[l] <= base)l++;
        arr[r] = arr[l];
    }
    arr[r] = base;
    quickSort2(arr, left, r - 1);
    quickSort2(arr, r + 1, right);
}